package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202409;

public class leetcode20240910 {
    /**
     * 统计上升四元组：非常好的解法
     * if(0<=i<j<k<l && nums[i]<nums[k]<nums[j]<nums[l]) cnt++;
     *
     * i<j<k<l
     * nums[i]<nums[k]<nums[j]<nums[l]
     *
     * 固定 j 和 k
     * 设 i 在 [0,j] 中间有多少nums[i]<nums[k]，记为pre[j][nums[k]]
     * 当nums[j-1]<nums[k]时
     *      pre[j][nums[k]]=pre[j-1][nums[k]]+1
     *  否则
     *      pre[j][nums[k]]=pre[j-1][nums[k]]
     *
     *  设l在[k+1,n]中间有多少nums[l]>nums[j]，记为post[k][nums[j]]
     *  当nums[k+1]>nums[j]时
     *      post[k][nums[j]]=post[k+1][nums[j]]+1
     *  否则
     *      post[k][nums[j]]=post[k+1][nums[j]]
     * @param nums
     * @return
     */
    public long countQuadruplets(int[] nums) {
        int n=nums.length;
        int[][] pre=new int[n+1][n+1];
        int[][] post=new int[n+1][n+1];

        for(int j=1;j<n;j++){
            for(int v=1;v<=n;v++){
                if(nums[j-1]<v){
                    pre[j][v]=pre[j-1][v]+1;
                }else{
                    pre[j][v]=pre[j-1][v];
                }
            }
        }

        for(int k=n-2;k>=0;k--){
            for(int v=1;v<=n;v++){
                if(nums[k+1]>v){
                    post[k][v]=post[k+1][v]+1;
                }else{
                    post[k][v]=post[k+1][v];
                }
            }
        }

        long ans=0L;
        for(int j=0;j<n;j++){
            for(int k=j+1;k<n;k++){
                if(nums[j]>nums[k]){
                    long t1=pre[j][nums[k]];
                    long t2=post[k][nums[j]];
                    ans+=t1*t2;
                }
            }
        }
        return ans;
    }
}
